/*-------------------------------------------------------------------------
 *
 * spgscan.c
 *	  SP-GiST 索引扫描的例程
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/access/spgist/spgscan.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/genam.h"
#include "access/relscan.h"
#include "access/spgist_private.h"
#include "miscadmin.h"
#include "pgstat.h"
#include "storage/bufmgr.h"
#include "utils/datum.h"
#include "utils/float.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"

typedef void (*storeRes_func) (SpGistScanOpaque so, ItemPointer heapPtr,
							   Datum leafValue, bool isNull,
							   SpGistLeafTuple leafTuple, bool recheck,
							   bool recheckDistances, double *distances);

/*
 * SpGistSearchItem 队列的成对堆比较函数。
 * KNN 搜索当前只支持 NULLS LAST。因此，在此保留该逻辑。
 */
static int fc_pairingheap_SpGistSearchItem_cmp(const pairingheap_node *fc_a,
								 const pairingheap_node *fc_b, void *fc_arg)
{
	const SpGistSearchItem *fc_sa = (const SpGistSearchItem *) fc_a;
	const SpGistSearchItem *fc_sb = (const SpGistSearchItem *) fc_b;
	SpGistScanOpaque fc_so = (SpGistScanOpaque) fc_arg;
	int			fc_i;

	if (fc_sa->isNull)
	{
		if (!fc_sb->isNull)
			return -1;
	}
	else if (fc_sb->isNull)
	{
		return 1;
	}
	else
	{
		/* 按照距离比较进行排序 */
		for (fc_i = 0; fc_i < fc_so->numberOfNonNullOrderBys; fc_i++)
		{
			if (isnan(fc_sa->distances[fc_i]) && isnan(fc_sb->distances[fc_i]))
				continue;		/* NaN == NaN */
			if (isnan(fc_sa->distances[fc_i]))
				return -1;		/* NaN > number */
			if (isnan(fc_sb->distances[fc_i]))
				return 1;		/* number < NaN */
			if (fc_sa->distances[fc_i] != fc_sb->distances[fc_i])
				return (fc_sa->distances[fc_i] < fc_sb->distances[fc_i]) ? 1 : -1;
		}
	}

	/* 叶子项在内页之前，以确保深度优先搜索 */
	if (fc_sa->isLeaf && !fc_sb->isLeaf)
		return 1;
	if (!fc_sa->isLeaf && fc_sb->isLeaf)
		return -1;

	return 0;
}

static void fc_spgFreeSearchItem(SpGistScanOpaque fc_so, SpGistSearchItem *fc_item)
{
	/* 如果是叶子，则 value 的类型为 attType，否则为 attLeafType */
	/* （不，这不是反向的；是的，这很混淆） */
	if (!(fc_item->isLeaf ? fc_so->state.attType.attbyval :
		  fc_so->state.attLeafType.attbyval) &&
		DatumGetPointer(fc_item->value) != NULL)
		pfree(DatumGetPointer(fc_item->value));

	if (fc_item->leafTuple)
		pfree(fc_item->leafTuple);

	if (fc_item->traversalValue)
		pfree(fc_item->traversalValue);

	pfree(fc_item);
}

/*
 * 将 SpGistSearchItem 添加到队列
 *
 * 在队列上下文中调用
 */
static void fc_spgAddSearchItemToQueue(SpGistScanOpaque fc_so, SpGistSearchItem *fc_item)
{
	pairingheap_add(fc_so->scanQueue, &fc_item->phNode);
}

static SpGistSearchItem * fc_spgAllocSearchItem(SpGistScanOpaque fc_so, bool fc_isnull, double *fc_distances)
{
	/* 仅为非 NULL 项分配距离数组 */
	SpGistSearchItem *fc_item =
	palloc(SizeOfSpGistSearchItem(fc_isnull ? 0 : fc_so->numberOfNonNullOrderBys));

	fc_item->isNull = fc_isnull;

	if (!fc_isnull && fc_so->numberOfNonNullOrderBys > 0)
		memcpy(fc_item->distances, fc_distances,
			   sizeof(fc_item->distances[0]) * fc_so->numberOfNonNullOrderBys);

	return fc_item;
}

static void fc_spgAddStartItem(SpGistScanOpaque fc_so, bool fc_isnull)
{
	SpGistSearchItem *fc_startEntry =
	fc_spgAllocSearchItem(fc_so, fc_isnull, fc_so->zeroDistances);

	ItemPointerSet(&fc_startEntry->heapPtr,
				   fc_isnull ? SPGIST_NULL_BLKNO : SPGIST_ROOT_BLKNO,
				   FirstOffsetNumber);
	fc_startEntry->isLeaf = false;
	fc_startEntry->level = 0;
	fc_startEntry->value = (Datum) 0;
	fc_startEntry->leafTuple = NULL;
	fc_startEntry->traversalValue = NULL;
	fc_startEntry->recheck = false;
	fc_startEntry->recheckDistances = false;

	fc_spgAddSearchItemToQueue(fc_so, fc_startEntry);
}

/*
 * 初始化队列以搜索根页面，重置
 * 任何先前活跃的扫描
 */
static void fc_resetSpGistScanOpaque(SpGistScanOpaque fc_so)
{
	MemoryContext fc_oldCtx;

	MemoryContextReset(fc_so->traversalCxt);

	fc_oldCtx = MemoryContextSwitchTo(fc_so->traversalCxt);

	/* 仅为距离排序的扫描初始化队列 */
	fc_so->scanQueue = pairingheap_allocate(fc_pairingheap_SpGistSearchItem_cmp, fc_so);

	if (fc_so->searchNulls)
		/* 添加工作项以扫描 NULL 索引条目 */
		fc_spgAddStartItem(fc_so, true);

	if (fc_so->searchNonNulls)
		/* 添加工作项以扫描非 NULL 索引条目 */
		fc_spgAddStartItem(fc_so, false);

	MemoryContextSwitchTo(fc_oldCtx);

	if (fc_so->numberOfOrderBys > 0)
	{
		/* 必须 pfree distances 以避免内存泄漏 */
		int			fc_i;

		for (fc_i = 0; fc_i < fc_so->nPtrs; fc_i++)
			if (fc_so->distances[fc_i])
				pfree(fc_so->distances[fc_i]);
	}

	if (fc_so->want_itup)
	{
		/* 必须 pfree 重构的元组以避免内存泄漏 */
		int			fc_i;

		for (fc_i = 0; fc_i < fc_so->nPtrs; fc_i++)
			pfree(fc_so->reconTups[fc_i]);
	}
	fc_so->iPtr = fc_so->nPtrs = 0;
}

/*
 * 从调用者提供的扫描键准备 SpGistScanOpaque 中的扫描键
 *
 * 设置 *so 的 searchNulls、searchNonNulls、numberOfKeys、keyData 字段。
 *
 * 这里的重点是消除与空值相关的考虑，以便运算符类一致性函数
 * 需要处理。我们假设所有可 SPGiST 索引的运算符都是严格的，因此任何空的 RHS 值
 * 使扫描条件不可满足。我们还提取任何 IS NULL/IS NOT NULL
 * 条件；它们的效果反映在 searchNulls/searchNonNulls 中。
 */
static void fc_spgPrepareScanKeys(IndexScanDesc fc_scan)
{
	SpGistScanOpaque fc_so = (SpGistScanOpaque) fc_scan->opaque;
	bool		fc_qual_ok;
	bool		fc_haveIsNull;
	bool		fc_haveNotNull;
	int			fc_nkeys;
	int			fc_i;

	fc_so->numberOfOrderBys = fc_scan->numberOfOrderBys;
	fc_so->orderByData = fc_scan->orderByData;

	if (fc_so->numberOfOrderBys <= 0)
		fc_so->numberOfNonNullOrderBys = 0;
	else
	{
		int			fc_j = 0;

		/*
		 * 删除所有 NULL 键，但记住它们在原始
		 * 数组中的偏移量。
		 */
		for (fc_i = 0; fc_i < fc_scan->numberOfOrderBys; fc_i++)
		{
			ScanKey		fc_skey = &fc_so->orderByData[fc_i];

			if (fc_skey->sk_flags & SK_ISNULL)
				fc_so->nonNullOrderByOffsets[fc_i] = -1;
			else
			{
				if (fc_i != fc_j)
					fc_so->orderByData[fc_j] = *fc_skey;

				fc_so->nonNullOrderByOffsets[fc_i] = fc_j++;
			}
		}

		fc_so->numberOfNonNullOrderBys = fc_j;
	}

	if (fc_scan->numberOfKeys <= 0)
	{
		/* 如果没有 quals，则需要全索引扫描 */
		fc_so->searchNulls = true;
		fc_so->searchNonNulls = true;
		fc_so->numberOfKeys = 0;
		return;
	}

	/* 检查给定的 quals */
	fc_qual_ok = true;
	fc_haveIsNull = fc_haveNotNull = false;
	fc_nkeys = 0;
	for (fc_i = 0; fc_i < fc_scan->numberOfKeys; fc_i++)
	{
		ScanKey		fc_skey = &fc_scan->keyData[fc_i];

		if (fc_skey->sk_flags & SK_SEARCHNULL)
			fc_haveIsNull = true;
		else if (fc_skey->sk_flags & SK_SEARCHNOTNULL)
			fc_haveNotNull = true;
		else if (fc_skey->sk_flags & SK_ISNULL)
		{
			/* 带有 NULL 参数的普通 quals - 不可满足 */
			fc_qual_ok = false;
			break;
		}
		else
		{
			/* 普通 quals，传播到 so->keyData */
			fc_so->keyData[fc_nkeys++] = *fc_skey;
			/* 这实际上创建了一个非 NULL 的要求 */
			fc_haveNotNull = true;
		}
	}

	/* IS NULL 与其他条件组合时是不可满足的 */
	if (fc_haveIsNull && fc_haveNotNull)
		fc_qual_ok = false;

	/* 发出结果 */
	if (fc_qual_ok)
	{
		fc_so->searchNulls = fc_haveIsNull;
		fc_so->searchNonNulls = fc_haveNotNull;
		fc_so->numberOfKeys = fc_nkeys;
	}
	else
	{
		fc_so->searchNulls = false;
		fc_so->searchNonNulls = false;
		fc_so->numberOfKeys = 0;
	}
}

IndexScanDesc spgbeginscan(Relation fc_rel, int fc_keysz, int fc_orderbysz)
{
	IndexScanDesc fc_scan;
	SpGistScanOpaque fc_so;
	int			fc_i;

	fc_scan = RelationGetIndexScan(fc_rel, fc_keysz, fc_orderbysz);

	fc_so = (SpGistScanOpaque) palloc0(sizeof(SpGistScanOpaqueData));
	if (fc_keysz > 0)
		fc_so->keyData = (ScanKey) palloc(sizeof(ScanKeyData) * fc_keysz);
	else
		fc_so->keyData = NULL;
	initSpGistState(&fc_so->state, fc_scan->indexRelation);

	fc_so->tempCxt = AllocSetContextCreate(CurrentMemoryContext,
										"SP-GiST search temporary context",
										ALLOCSET_DEFAULT_SIZES);
	fc_so->traversalCxt = AllocSetContextCreate(CurrentMemoryContext,
											 "SP-GiST traversal-value context",
											 ALLOCSET_DEFAULT_SIZES);

	/*
	 * 设置 reconTupDesc 和 xs_hitupdesc 以防它是一个仅索引扫描，
	 * 确保键列被显示为类型 attType。
	 * （在可能浪费工作时进行此操作相当烦人，但对于
	 * 大多数运算符类，我们可以重复使用索引 reldesc，而不是创建一个。）
	 */
	fc_so->reconTupDesc = fc_scan->xs_hitupdesc =
		getSpGistTupleDesc(fc_rel, &fc_so->state.attType);

	/* 为排序扫描分配所需的各种数组 */
	if (fc_scan->numberOfOrderBys > 0)
	{
		/* 这将在 spgrescan 中填写，但在此分配空间 */
		fc_so->orderByTypes = (Oid *)
			palloc(sizeof(Oid) * fc_scan->numberOfOrderBys);
		fc_so->nonNullOrderByOffsets = (int *)
			palloc(sizeof(int) * fc_scan->numberOfOrderBys);

		/* 这些数组具有恒定内容，因此我们现在可以填写它们 */
		fc_so->zeroDistances = (double *)
			palloc(sizeof(double) * fc_scan->numberOfOrderBys);
		fc_so->infDistances = (double *)
			palloc(sizeof(double) * fc_scan->numberOfOrderBys);

		for (fc_i = 0; fc_i < fc_scan->numberOfOrderBys; fc_i++)
		{
			fc_so->zeroDistances[fc_i] = 0.0;
			fc_so->infDistances[fc_i] = get_float8_infinity();
		}

		fc_scan->xs_orderbyvals = (Datum *)
			palloc0(sizeof(Datum) * fc_scan->numberOfOrderBys);
		fc_scan->xs_orderbynulls = (bool *)
			palloc(sizeof(bool) * fc_scan->numberOfOrderBys);
		memset(fc_scan->xs_orderbynulls, true,
			   sizeof(bool) * fc_scan->numberOfOrderBys);
	}

	fmgr_info_copy(&fc_so->innerConsistentFn,
				   index_getprocinfo(fc_rel, 1, SPGIST_INNER_CONSISTENT_PROC),
				   CurrentMemoryContext);

	fmgr_info_copy(&fc_so->leafConsistentFn,
				   index_getprocinfo(fc_rel, 1, SPGIST_LEAF_CONSISTENT_PROC),
				   CurrentMemoryContext);

	fc_so->indexCollation = fc_rel->rd_indcollation[0];

	fc_scan->opaque = fc_so;

	return fc_scan;
}

void spgrescan(IndexScanDesc fc_scan, ScanKey fc_scankey, int fc_nscankeys,
		  ScanKey fc_orderbys, int fc_norderbys)
{
	SpGistScanOpaque fc_so = (SpGistScanOpaque) fc_scan->opaque;

	/* 将 scankeys 复制到本地存储 */
	if (fc_scankey && fc_scan->numberOfKeys > 0)
		memmove(fc_scan->keyData, fc_scankey,
				fc_scan->numberOfKeys * sizeof(ScanKeyData));

	/* 如果需要，初始化排序数据 */
	if (fc_orderbys && fc_scan->numberOfOrderBys > 0)
	{
		int			fc_i;

		memmove(fc_scan->orderByData, fc_orderbys,
				fc_scan->numberOfOrderBys * sizeof(ScanKeyData));

		for (fc_i = 0; fc_i < fc_scan->numberOfOrderBys; fc_i++)
		{
			ScanKey		fc_skey = &fc_scan->orderByData[fc_i];

			/*
			 * 查找原始排序操作符返回的数据类型。
			 * SP-GiST 始终使用 float8 作为距离函数，但排序操作符可以是其他任何东西。
			 *
			 * XXX: 仅当排序操作符的结果类型为 float4 或 float8 时，距离函数才被允许为有损的。
			 * 否则我们不知道如何将距离返回给执行器。
			 * 但我们不能在这里检查，因为我们不知道距离函数在第一次返回 *recheck = true
			 * 之前是否有损。
			 */
			fc_so->orderByTypes[fc_i] = get_func_rettype(fc_skey->sk_func.fn_oid);
		}
	}

	/* 预处理扫描键，在 *so 中设置表示 */
	fc_spgPrepareScanKeys(fc_scan);

	/* 设置起始队列条目 */
	fc_resetSpGistScanOpaque(fc_so);

	/* 统计索引扫描的计数 */
	pgstat_count_index_scan(fc_scan->indexRelation);
}

void spgendscan(IndexScanDesc fc_scan)
{
	SpGistScanOpaque fc_so = (SpGistScanOpaque) fc_scan->opaque;

	MemoryContextDelete(fc_so->tempCxt);
	MemoryContextDelete(fc_so->traversalCxt);

	if (fc_so->keyData)
		pfree(fc_so->keyData);

	if (fc_so->state.leafTupDesc &&
		fc_so->state.leafTupDesc != RelationGetDescr(fc_so->state.index))
		FreeTupleDesc(fc_so->state.leafTupDesc);

	if (fc_so->state.deadTupleStorage)
		pfree(fc_so->state.deadTupleStorage);

	if (fc_scan->numberOfOrderBys > 0)
	{
		pfree(fc_so->orderByTypes);
		pfree(fc_so->nonNullOrderByOffsets);
		pfree(fc_so->zeroDistances);
		pfree(fc_so->infDistances);
		pfree(fc_scan->xs_orderbyvals);
		pfree(fc_scan->xs_orderbynulls);
	}

	pfree(fc_so);
}

/*
 * Leaf SpGistSearchItem 构造函数，在队列上下文中调用
 */
static SpGistSearchItem * fc_spgNewHeapItem(SpGistScanOpaque fc_so, int fc_level, SpGistLeafTuple fc_leafTuple,
			   Datum fc_leafValue, bool fc_recheck, bool fc_recheckDistances,
			   bool fc_isnull, double *fc_distances)
{
	SpGistSearchItem *fc_item = fc_spgAllocSearchItem(fc_so, fc_isnull, fc_distances);

	fc_item->level = fc_level;
	fc_item->heapPtr = fc_leafTuple->heapPtr;

	/*
	 * 如果我们需要重建值，将其从临时上下文复制到队列上下文。
	 * 注意：如果我们没有要求，leaf_consistent 方法可能没有提供值，
	 * 并且轻微损坏的方法可能会提供错误类型的值。
	 * 正确的 leafValue 类型是 attType 而不是 leafType。
	 */
	if (fc_so->want_itup)
	{
		fc_item->value = fc_isnull ? (Datum) 0 :
			datumCopy(fc_leafValue, fc_so->state.attType.attbyval,
					  fc_so->state.attType.attlen);

		/*
		 * 如果我们需要重建 INCLUDE 属性，存储整个叶元组，以便可以从中获取 INCLUDE 属性。
		 */
		if (fc_so->state.leafTupDesc->natts > 1)
		{
			fc_item->leafTuple = palloc(fc_leafTuple->size);
			memcpy(fc_item->leafTuple, fc_leafTuple, fc_leafTuple->size);
		}
		else
			fc_item->leafTuple = NULL;
	}
	else
	{
		fc_item->value = (Datum) 0;
		fc_item->leafTuple = NULL;
	}
	fc_item->traversalValue = NULL;
	fc_item->isLeaf = true;
	fc_item->recheck = fc_recheck;
	fc_item->recheckDistances = fc_recheckDistances;

	return fc_item;
}

/*
 * 测试叶元组是否满足所有扫描键
 *
 * *reportedSome 在以下情况下设置为 true：
 *		扫描未排序且项目满足扫描键
 */
static bool fc_spgLeafTest(SpGistScanOpaque fc_so, SpGistSearchItem *fc_item,
			SpGistLeafTuple fc_leafTuple, bool fc_isnull,
			bool *fc_reportedSome, storeRes_func fc_storeRes)
{
	Datum		fc_leafValue;
	double	   *fc_distances;
	bool		fc_result;
	bool		fc_recheck;
	bool		fc_recheckDistances;

	if (fc_isnull)
	{
		/* 除非需要空值，否则不应到达空值页面 */
		Assert(fc_so->searchNulls);
		fc_leafValue = (Datum) 0;
		fc_distances = NULL;
		fc_recheck = false;
		fc_recheckDistances = false;
		fc_result = true;
	}
	else
	{
		spgLeafConsistentIn fc_in;
		spgLeafConsistentOut fc_out;

		/* 使用临时上下文调用 leaf_consistent */
		MemoryContext fc_oldCxt = MemoryContextSwitchTo(fc_so->tempCxt);

		fc_in.scankeys = fc_so->keyData;
		fc_in.nkeys = fc_so->numberOfKeys;
		fc_in.orderbys = fc_so->orderByData;
		fc_in.norderbys = fc_so->numberOfNonNullOrderBys;
		Assert(!fc_item->isLeaf);	/* 否则 reconstructedValue 将是错误的类型 */
		fc_in.reconstructedValue = fc_item->value;
		fc_in.traversalValue = fc_item->traversalValue;
		fc_in.level = fc_item->level;
		fc_in.returnData = fc_so->want_itup;
		fc_in.leafDatum = SGLTDATUM(fc_leafTuple, &fc_so->state);

		fc_out.leafValue = (Datum) 0;
		fc_out.recheck = false;
		fc_out.distances = NULL;
		fc_out.recheckDistances = false;

		fc_result = DatumGetBool(FunctionCall2Coll(&fc_so->leafConsistentFn,
												fc_so->indexCollation,
												PointerGetDatum(&fc_in),
												PointerGetDatum(&fc_out)));
		fc_recheck = fc_out.recheck;
		fc_recheckDistances = fc_out.recheckDistances;
		fc_leafValue = fc_out.leafValue;
		fc_distances = fc_out.distances;

		MemoryContextSwitchTo(fc_oldCxt);
	}

	if (fc_result)
	{
		/* 项目通过扫描键 */
		if (fc_so->numberOfNonNullOrderBys > 0)
		{
			/* 扫描是有序的 -> 将项目添加到队列 */
			MemoryContext fc_oldCxt = MemoryContextSwitchTo(fc_so->traversalCxt);
			SpGistSearchItem *fc_heapItem = fc_spgNewHeapItem(fc_so, fc_item->level,
														fc_leafTuple,
														fc_leafValue,
														fc_recheck,
														fc_recheckDistances,
														fc_isnull,
														fc_distances);

			fc_spgAddSearchItemToQueue(fc_so, fc_heapItem);

			MemoryContextSwitchTo(fc_oldCxt);
		}
		else
		{
			/* 非有序扫描，因此立即报告该项目 */
			Assert(!fc_recheckDistances);
			fc_storeRes(fc_so, &fc_leafTuple->heapPtr, fc_leafValue, fc_isnull,
					 fc_leafTuple, fc_recheck, false, NULL);
			*fc_reportedSome = true;
		}
	}

	return fc_result;
}

/* inner_consistent 方法的包初始化器 */
static void fc_spgInitInnerConsistentIn(spgInnerConsistentIn *fc_in,
						 SpGistScanOpaque fc_so,
						 SpGistSearchItem *fc_item,
						 SpGistInnerTuple fc_innerTuple)
{
	fc_in->scankeys = fc_so->keyData;
	fc_in->orderbys = fc_so->orderByData;
	fc_in->nkeys = fc_so->numberOfKeys;
	fc_in->norderbys = fc_so->numberOfNonNullOrderBys;
	Assert(!fc_item->isLeaf);		/* 否则 reconstructedValue 将是错误的类型 */
	fc_in->reconstructedValue = fc_item->value;
	fc_in->traversalMemoryContext = fc_so->traversalCxt;
	fc_in->traversalValue = fc_item->traversalValue;
	fc_in->level = fc_item->level;
	fc_in->returnData = fc_so->want_itup;
	fc_in->allTheSame = fc_innerTuple->allTheSame;
	fc_in->hasPrefix = (fc_innerTuple->prefixSize > 0);
	fc_in->prefixDatum = SGITDATUM(fc_innerTuple, &fc_so->state);
	fc_in->nNodes = fc_innerTuple->nNodes;
	fc_in->nodeLabels = spgExtractNodeLabels(&fc_so->state, fc_innerTuple);
}

static SpGistSearchItem * fc_spgMakeInnerItem(SpGistScanOpaque fc_so,
				 SpGistSearchItem *fc_parentItem,
				 SpGistNodeTuple fc_tuple,
				 spgInnerConsistentOut *fc_out, int fc_i, bool fc_isnull,
				 double *fc_distances)
{
	SpGistSearchItem *fc_item = fc_spgAllocSearchItem(fc_so, fc_isnull, fc_distances);

	fc_item->heapPtr = fc_tuple->t_tid;
	fc_item->level = fc_out->levelAdds ? fc_parentItem->level + fc_out->levelAdds[fc_i]
		: fc_parentItem->level;

	/* 必须将值复制出临时上下文 */
	/* （回忆一下重建值的类型是 leafType） */
	fc_item->value = fc_out->reconstructedValues
		? datumCopy(fc_out->reconstructedValues[fc_i],
					fc_so->state.attLeafType.attbyval,
					fc_so->state.attLeafType.attlen)
		: (Datum) 0;

	fc_item->leafTuple = NULL;

	/*
	 * out.traversalValues 的元素应该在
	 * in.traversalMemoryContext 中分配，这实际上是一个长期存在的索引扫描上下文。
	 */
	fc_item->traversalValue =
		fc_out->traversalValues ? fc_out->traversalValues[fc_i] : NULL;

	fc_item->isLeaf = false;
	fc_item->recheck = false;
	fc_item->recheckDistances = false;

	return fc_item;
}

static void fc_spgInnerTest(SpGistScanOpaque fc_so, SpGistSearchItem *fc_item,
			 SpGistInnerTuple fc_innerTuple, bool fc_isnull)
{
	MemoryContext fc_oldCxt = MemoryContextSwitchTo(fc_so->tempCxt);
	spgInnerConsistentOut fc_out;
	int			fc_nNodes = fc_innerTuple->nNodes;
	int			fc_i;

	memset(&fc_out, 0, sizeof(fc_out));

	if (!fc_isnull)
	{
		spgInnerConsistentIn fc_in;

		fc_spgInitInnerConsistentIn(&fc_in, fc_so, fc_item, fc_innerTuple);

		/* 使用用户定义的内部一致性方法 */
		FunctionCall2Coll(&fc_so->innerConsistentFn,
						  fc_so->indexCollation,
						  PointerGetDatum(&fc_in),
						  PointerGetDatum(&fc_out));
	}
	else
	{
		/* 强制访问所有子项 */
		fc_out.nNodes = fc_nNodes;
		fc_out.nodeNumbers = (int *) palloc(sizeof(int) * fc_nNodes);
		for (fc_i = 0; fc_i < fc_nNodes; fc_i++)
			fc_out.nodeNumbers[fc_i] = fc_i;
	}

	/* 如果全相同，它们应该全部匹配或都不匹配 */
	if (fc_innerTuple->allTheSame && fc_out.nNodes != 0 && fc_out.nNodes != fc_nNodes)
		elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");

	if (fc_out.nNodes)
	{
		/* 收集节点指针 */
		SpGistNodeTuple fc_node;
		SpGistNodeTuple *fc_nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) * fc_nNodes);

		SGITITERATE(fc_innerTuple, fc_i, fc_node)
		{
			fc_nodes[fc_i] = fc_node;
		}

		MemoryContextSwitchTo(fc_so->traversalCxt);

		for (fc_i = 0; fc_i < fc_out.nNodes; fc_i++)
		{
			int			fc_nodeN = fc_out.nodeNumbers[fc_i];
			SpGistSearchItem *fc_innerItem;
			double	   *fc_distances;

			Assert(fc_nodeN >= 0 && fc_nodeN < fc_nNodes);

			fc_node = fc_nodes[fc_nodeN];

			if (!ItemPointerIsValid(&fc_node->t_tid))
				continue;

			/*
			 * 如果 innerConsistentFn() 未能返回
			 * 距离或是 NULL 项（它们的距离实际上未使用），则使用无穷大距离。
			 */
			fc_distances = fc_out.distances ? fc_out.distances[fc_i] : fc_so->infDistances;

			fc_innerItem = fc_spgMakeInnerItem(fc_so, fc_item, fc_node, &fc_out, fc_i, fc_isnull,
										 fc_distances);

			fc_spgAddSearchItemToQueue(fc_so, fc_innerItem);
		}
	}

	MemoryContextSwitchTo(fc_oldCxt);
}

/* 返回有序扫描中的下一个项，或如果索引耗尽则返回 null */
static SpGistSearchItem * fc_spgGetNextQueueItem(SpGistScanOpaque fc_so)
{
	if (pairingheap_is_empty(fc_so->scanQueue))
		return NULL;			/* 当两个堆均为空时完成 */

	/* 返回项目；调用者负责释放它 */
	return (SpGistSearchItem *) pairingheap_remove_first(fc_so->scanQueue);
}

enum SpGistSpecialOffsetNumbers
{
	SpGistBreakOffsetNumber = InvalidOffsetNumber,
	SpGistRedirectOffsetNumber = MaxOffsetNumber + 1,
	SpGistErrorOffsetNumber = MaxOffsetNumber + 2
};

static OffsetNumber fc_spgTestLeafTuple(SpGistScanOpaque fc_so,
				 SpGistSearchItem *fc_item,
				 Page fc_page, OffsetNumber fc_offset,
				 bool fc_isnull, bool fc_isroot,
				 bool *fc_reportedSome,
				 storeRes_func fc_storeRes)
{
	SpGistLeafTuple fc_leafTuple = (SpGistLeafTuple)
	PageGetItem(fc_page, PageGetItemId(fc_page, fc_offset));

	if (fc_leafTuple->tupstate != SPGIST_LIVE)
	{
		if (!fc_isroot)			/* 根上的所有元组应该是活动的 */
		{
			if (fc_leafTuple->tupstate == SPGIST_REDIRECT)
			{
				/* 重定向元组应该是链中的第一个 */
				Assert(fc_offset == ItemPointerGetOffsetNumber(&fc_item->heapPtr));
				/* 将注意力转移到重定向点 */
				fc_item->heapPtr = ((SpGistDeadTuple) fc_leafTuple)->pointer;
				Assert(ItemPointerGetBlockNumber(&fc_item->heapPtr) != SPGIST_METAPAGE_BLKNO);
				return SpGistRedirectOffsetNumber;
			}

			if (fc_leafTuple->tupstate == SPGIST_DEAD)
			{
				/* 死元组应该是链中的第一个 */
				Assert(fc_offset == ItemPointerGetOffsetNumber(&fc_item->heapPtr));
				/* 此页面上没有活动条目 */
				Assert(SGLT_GET_NEXTOFFSET(fc_leafTuple) == InvalidOffsetNumber);
				return SpGistBreakOffsetNumber;
			}
		}

		/* 我们不应该到达占位符 */
		elog(ERROR, "unexpected SPGiST tuple state: %d", fc_leafTuple->tupstate);
		return SpGistErrorOffsetNumber;
	}

	Assert(ItemPointerIsValid(&fc_leafTuple->heapPtr));

	fc_spgLeafTest(fc_so, fc_item, fc_leafTuple, fc_isnull, fc_reportedSome, fc_storeRes);

	return SGLT_GET_NEXTOFFSET(fc_leafTuple);
}

/*
 * 遍历树并将所有符合扫描资格的元组报告给storeRes
 * 子例程。
 *
 * 如果scanWholeIndex为真，我们就这样做。如果不是，一旦我们报告了至少一个元组，
 * 我们将停止在下一个页面边界。
 */
static void fc_spgWalk(Relation fc_index, SpGistScanOpaque fc_so, bool fc_scanWholeIndex,
		storeRes_func fc_storeRes, Snapshot fc_snapshot)
{
	Buffer		fc_buffer = InvalidBuffer;
	bool		fc_reportedSome = false;

	while (fc_scanWholeIndex || !fc_reportedSome)
	{
		SpGistSearchItem *fc_item = fc_spgGetNextQueueItem(fc_so);

		if (fc_item == NULL)
			break;				/* 队列中没有更多项目 -> 完成 */

redirect:
		/* 检查中断，以防出现无限循环 */
		CHECK_FOR_INTERRUPTS();

		if (fc_item->isLeaf)
		{
			/* 我们只在有序搜索的情况下将堆项目存储在队列中 */
			Assert(fc_so->numberOfNonNullOrderBys > 0);
			fc_storeRes(fc_so, &fc_item->heapPtr, fc_item->value, fc_item->isNull,
					 fc_item->leafTuple, fc_item->recheck,
					 fc_item->recheckDistances, fc_item->distances);
			fc_reportedSome = true;
		}
		else
		{
			BlockNumber fc_blkno = ItemPointerGetBlockNumber(&fc_item->heapPtr);
			OffsetNumber fc_offset = ItemPointerGetOffsetNumber(&fc_item->heapPtr);
			Page		fc_page;
			bool		fc_isnull;

			if (fc_buffer == InvalidBuffer)
			{
				fc_buffer = ReadBuffer(fc_index, fc_blkno);
				LockBuffer(fc_buffer, BUFFER_LOCK_SHARE);
			}
			else if (fc_blkno != BufferGetBlockNumber(fc_buffer))
			{
				UnlockReleaseBuffer(fc_buffer);
				fc_buffer = ReadBuffer(fc_index, fc_blkno);
				LockBuffer(fc_buffer, BUFFER_LOCK_SHARE);
			}

			/* 否则新指针指向相同的页面，无需工作 */

			fc_page = BufferGetPage(fc_buffer);
			TestForOldSnapshot(fc_snapshot, fc_index, fc_page);

			fc_isnull = SpGistPageStoresNulls(fc_page) ? true : false;

			if (SpGistPageIsLeaf(fc_page))
			{
				/* 页面是一个叶子 - 也就是说，它的所有元组都是堆项目 */
				OffsetNumber fc_max = PageGetMaxOffsetNumber(fc_page);

				if (SpGistBlockIsRoot(fc_blkno))
				{
					/* 当根是一个叶子时，检查它的所有元组 */
					for (fc_offset = FirstOffsetNumber; fc_offset <= fc_max; fc_offset++)
						(void) fc_spgTestLeafTuple(fc_so, fc_item, fc_page, fc_offset,
												fc_isnull, true,
												&fc_reportedSome, fc_storeRes);
				}
				else
				{
					/* 正常情况：只检查我们到达的链 */
					while (fc_offset != InvalidOffsetNumber)
					{
						Assert(fc_offset >= FirstOffsetNumber && fc_offset <= fc_max);
						fc_offset = fc_spgTestLeafTuple(fc_so, fc_item, fc_page, fc_offset,
												  fc_isnull, false,
												  &fc_reportedSome, fc_storeRes);
						if (fc_offset == SpGistRedirectOffsetNumber)
							goto redirect;
					}
				}
			}
			else				/* 页面是内部节点 */
			{
				SpGistInnerTuple fc_innerTuple = (SpGistInnerTuple)
				PageGetItem(fc_page, PageGetItemId(fc_page, fc_offset));

				if (fc_innerTuple->tupstate != SPGIST_LIVE)
				{
					if (fc_innerTuple->tupstate == SPGIST_REDIRECT)
					{
						/* 将注意力转移到重定向点 */
						fc_item->heapPtr = ((SpGistDeadTuple) fc_innerTuple)->pointer;
						Assert(ItemPointerGetBlockNumber(&fc_item->heapPtr) !=
							   SPGIST_METAPAGE_BLKNO);
						goto redirect;
					}
					elog(ERROR, "unexpected SPGiST tuple state: %d",
						 fc_innerTuple->tupstate);
				}

				fc_spgInnerTest(fc_so, fc_item, fc_innerTuple, fc_isnull);
			}
		}

		/* 完成此扫描项目 */
		fc_spgFreeSearchItem(fc_so, fc_item);
		/* 在进行下一个之前清除临时上下文 */
		MemoryContextReset(fc_so->tempCxt);
	}

	if (fc_buffer != InvalidBuffer)
		UnlockReleaseBuffer(fc_buffer);
}


/* 针对getbitmap情况的storeRes子例程 */
static void fc_storeBitmap(SpGistScanOpaque fc_so, ItemPointer fc_heapPtr,
			Datum fc_leafValue, bool fc_isnull,
			SpGistLeafTuple fc_leafTuple, bool fc_recheck,
			bool fc_recheckDistances, double *fc_distances)
{
	Assert(!fc_recheckDistances && !fc_distances);
	tbm_add_tuples(fc_so->tbm, fc_heapPtr, 1, fc_recheck);
	fc_so->ntids++;
}

int64 spggetbitmap(IndexScanDesc fc_scan, TIDBitmap *fc_tbm)
{
	SpGistScanOpaque fc_so = (SpGistScanOpaque) fc_scan->opaque;

	/* 将want_itup复制到*so，这样我们就不需要单独传递它 */
	fc_so->want_itup = false;

	fc_so->tbm = fc_tbm;
	fc_so->ntids = 0;

	fc_spgWalk(fc_scan->indexRelation, fc_so, true, fc_storeBitmap, fc_scan->xs_snapshot);

	return fc_so->ntids;
}

/* 针对gettuple情况的storeRes子例程 */
static void fc_storeGettuple(SpGistScanOpaque fc_so, ItemPointer fc_heapPtr,
			  Datum fc_leafValue, bool fc_isnull,
			  SpGistLeafTuple fc_leafTuple, bool fc_recheck,
			  bool fc_recheckDistances, double *fc_nonNullDistances)
{
	Assert(fc_so->nPtrs < MaxIndexTuplesPerPage);
	fc_so->heapPtrs[fc_so->nPtrs] = *fc_heapPtr;
	fc_so->recheck[fc_so->nPtrs] = fc_recheck;
	fc_so->recheckDistances[fc_so->nPtrs] = fc_recheckDistances;

	if (fc_so->numberOfOrderBys > 0)
	{
		if (fc_isnull || fc_so->numberOfNonNullOrderBys <= 0)
			fc_so->distances[fc_so->nPtrs] = NULL;
		else
		{
			IndexOrderByDistance *fc_distances =
			palloc(sizeof(fc_distances[0]) * fc_so->numberOfOrderBys);
			int			fc_i;

			for (fc_i = 0; fc_i < fc_so->numberOfOrderBys; fc_i++)
			{
				int			fc_offset = fc_so->nonNullOrderByOffsets[fc_i];

				if (fc_offset >= 0)
				{
					/* 复制非NULL距离值 */
					fc_distances[fc_i].value = fc_nonNullDistances[fc_offset];
					fc_distances[fc_i].isnull = false;
				}
				else
				{
					/* 设置距离的NULL标志。 */
					fc_distances[fc_i].value = 0.0;
					fc_distances[fc_i].isnull = true;
				}
			}

			fc_so->distances[fc_so->nPtrs] = fc_distances;
		}
	}

	if (fc_so->want_itup)
	{
		/*
		 * 重构索引数据。我们必须将数据从临时上下文中复制出来，
		 * 所以我们可以在这里创建元组。
		 */
		Datum		fc_leafDatums[INDEX_MAX_KEYS];
		bool		fc_leafIsnulls[INDEX_MAX_KEYS];

		/* 只有在具有INCLUDE属性时，我们才需要变形旧元组 */
		if (fc_so->state.leafTupDesc->natts > 1)
			spgDeformLeafTuple(fc_leafTuple, fc_so->state.leafTupDesc,
							   fc_leafDatums, fc_leafIsnulls, fc_isnull);

		fc_leafDatums[spgKeyColumn] = fc_leafValue;
		fc_leafIsnulls[spgKeyColumn] = fc_isnull;

		fc_so->reconTups[fc_so->nPtrs] = heap_form_tuple(fc_so->reconTupDesc,
												   fc_leafDatums,
												   fc_leafIsnulls);
	}
	fc_so->nPtrs++;
}

bool spggettuple(IndexScanDesc fc_scan, ScanDirection fc_dir)
{
	SpGistScanOpaque fc_so = (SpGistScanOpaque) fc_scan->opaque;

	if (fc_dir != ForwardScanDirection)
		elog(ERROR, "SP-GiST only supports forward scan direction");

	/* 将want_itup复制到*so，这样我们就不需要单独传递它 */
	fc_so->want_itup = fc_scan->xs_want_itup;

	for (;;)
	{
		if (fc_so->iPtr < fc_so->nPtrs)
		{
			/* 继续返回已报告的元组 */
			fc_scan->xs_heaptid = fc_so->heapPtrs[fc_so->iPtr];
			fc_scan->xs_recheck = fc_so->recheck[fc_so->iPtr];
			fc_scan->xs_hitup = fc_so->reconTups[fc_so->iPtr];

			if (fc_so->numberOfOrderBys > 0)
				index_store_float8_orderby_distances(fc_scan, fc_so->orderByTypes,
													 fc_so->distances[fc_so->iPtr],
													 fc_so->recheckDistances[fc_so->iPtr]);
			fc_so->iPtr++;
			return true;
		}

		if (fc_so->numberOfOrderBys > 0)
		{
			/* 必须 pfree distances 以避免内存泄漏 */
			int			fc_i;

			for (fc_i = 0; fc_i < fc_so->nPtrs; fc_i++)
				if (fc_so->distances[fc_i])
					pfree(fc_so->distances[fc_i]);
		}

		if (fc_so->want_itup)
		{
			/* 必须 pfree 重构的元组以避免内存泄漏 */
			int			fc_i;

			for (fc_i = 0; fc_i < fc_so->nPtrs; fc_i++)
				pfree(fc_so->reconTups[fc_i]);
		}
		fc_so->iPtr = fc_so->nPtrs = 0;

		fc_spgWalk(fc_scan->indexRelation, fc_so, false, fc_storeGettuple,
				fc_scan->xs_snapshot);

		if (fc_so->nPtrs == 0)
			break;				/* 必须完成扫描 */
	}

	return false;
}

bool spgcanreturn(Relation fc_index, int fc_attno)
{
	SpGistCache *fc_cache;

	/* INCLUDE属性总是可以为仅索引扫描获取 */
	if (fc_attno > 1)
		return true;

	/* 如果opclass配置函数允许，我们可以这样做 */
	fc_cache = spgGetCache(fc_index);

	return fc_cache->config.canReturnData;
}
